Search Results

Documents authored by Abel, Zachary

Document
DOI: 10.4230/LIPIcs.FUN.2018.3
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

Authors: Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to have certain numbers of incident path edges (triangles); or forcing the regions formed by the path to be partially monochromatic (squares), have exactly two special cells (stars), or be singly covered by given shapes (polyominoes) and/or negatively counting shapes (antipolyominoes). We show that any one of these clue types (except the first) is enough to make path finding NP-complete ("witnesses exist but are hard to find"), even for rectangular boards. Furthermore, we show that a final clue type (antibody), which necessarily "cancels" the effect of another clue in the same region, makes path finding Sigma_2-complete ("witnesses do not exist"), even with a single antibody (combined with many anti/polyominoes), and the problem gets no harder with many antibodies.
Cite as

Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy. Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.FUN.2018.3,
  author =	{Abel, Zachary and Bosboom, Jeffrey and Demaine, Erik D. and Hamilton, Linus and Hesterberg, Adam and Kopinsky, Justin and Lynch, Jayson and Rudoy, Mikhail},
  title =	{{Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.3},
  URN =		{urn:nbn:de:0030-drops-87944},
  doi =		{10.4230/LIPIcs.FUN.2018.3},
  annote =	{Keywords: video games, puzzles, hardness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.3
Who Needs Crossings? Hardness of Plane Graph Rigidity

Authors: Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid crossings in all of their configurations; matchstick graphs, with unit-length edges and where only noncrossing configurations are considered; and unrestricted graphs (crossings allowed) with unit edge lengths (or in the global rigidity case, edge lengths in {1,2}). We show that all nine of these questions are complete for the class Exists-R, defined by the Existential Theory of the Reals, or its complement Forall-R; in particular, each problem is (co)NP-hard. One of these nine results - that realization of unit-distance graphs is Exists-R-complete - was shown previously by Schaefer (2013), but the other eight are new. We strengthen several prior results. Matchstick graph realization was known to be NP-hard (Eades & Wormald 1990, or Cabello et al. 2007), but its membership in NP remained open; we show it is complete for the (possibly) larger class Exists-R. Global rigidity of graphs with edge lengths in {1,2} was known to be coNP-hard (Saxe 1979); we show it is Forall-R-complete. The majority of the paper is devoted to proving an analog of Kempe's Universality Theorem - informally, "there is a linkage to sign your name" - for globally noncrossing linkages. In particular, we show that any polynomial curve phi(x,y)=0 can be traced by a noncrossing linkage, settling an open problem from 2004. More generally, we show that the nontrivial regions in the plane that may be traced by a noncrossing linkage are precisely the compact semialgebraic regions. Thus, no drawing power is lost by restricting to noncrossing linkages. We prove analogous results for matchstick linkages and unit-distance linkages as well.
Cite as

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl. Who Needs Crossings? Hardness of Plane Graph Rigidity. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.SoCG.2016.3,
  author =	{Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lynch, Jayson and Schardl, Tao B.},
  title =	{{Who Needs Crossings? Hardness of Plane Graph Rigidity}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.3},
  URN =		{urn:nbn:de:0030-drops-58951},
  doi =		{10.4230/LIPIcs.SoCG.2016.3},
  annote =	{Keywords: Graph Drawing, Graph Rigidity Theory, Graph Global Rigidity, Linkages, Complexity Theory, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.269
Algorithms for Designing Pop-Up Cards

Authors: Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We prove that every simple polygon can be made as a (2D) pop-up card/book that opens to any desired angle between 0 and 360°. More precisely, given a simple polygon attached to the two walls of the open pop-up, our polynomial-time algorithm subdivides the polygon into a single-degree-of-freedom linkage structure, such that closing the pop-up flattens the linkage without collision. This result solves an open problem of Hara and Sugihara from 2009. We also show how to obtain a more efficient construction for the special case of orthogonal polygons, and how to make 3D orthogonal polyhedra, from pop-ups that open to 90°, 180°, 270°, or 360°.
Cite as

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow. Algorithms for Designing Pop-Up Cards. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.STACS.2013.269,
  author =	{Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lubiw, Anna and Schulz, Andr\'{e} and Souvaine, Diane L. and Viglietta, Giovanni and Winslow, Andrew},
  title =	{{Algorithms for Designing Pop-Up Cards}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{269--280},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.269},
  URN =		{urn:nbn:de:0030-drops-39407},
  doi =		{10.4230/LIPIcs.STACS.2013.269},
  annote =	{Keywords: geometric folding, linkages, universality}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact